|
In graph theory, an undirected graph ''H'' is called a minor of the graph ''G'' if ''H'' can be formed from ''G'' by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors do not include the complete graph ''K''5 nor the complete bipartite graph ''K''3,3.〔, p. 77; .〕 The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions.〔, theorem 4, p. 78; .〕 For every fixed graph ''H'', it is possible to test whether ''H'' is a minor of an input graph ''G'' in polynomial time;〔 together with the forbidden minor characterization this implies that every graph property preserved by deletions and contractions may be recognized in polynomial time.〔 Other results and conjectures involving graph minors include the graph structure theorem, according to which the graphs that do not have ''H'' as a minor may be formed by gluing together simpler pieces, and Hadwiger's conjecture relating the inability to color a graph to the existence of a large complete graph as a minor of it. Important variants of graph minors include the topological minors and immersion minors. ==Definitions== An edge contraction is an operation which removes an edge from a graph while simultaneously merging the two vertices it used to connect. An undirected graph ''H'' is a minor of another undirected graph ''G'' if a graph isomorphic to ''H'' can be obtained from ''G'' by contracting some edges, deleting some edges, and deleting some isolated vertices. The order in which a sequence of such contractions and deletions is performed on ''G'' does not affect the resulting graph ''H''. Graph minors are often studied in the more general context of matroid minors. In this context, it is common to assume that all graphs are connected, with self-loops and multiple edges allowed (that is, they are multigraphs rather than simple graphs); the contraction of a loop and the deletion of a cut-edge are forbidden operations. This point of view has the advantage that edge deletions leave the rank of a graph unchanged, and edge contractions always reduce the rank by one. In other contexts (such as with the study of pseudoforests) it makes more sense to allow the deletion of a cut-edge, and to allow disconnected graphs, but to forbid multigraphs. In this variation of graph minor theory, a graph is always simplified after any edge contraction to eliminate its self-loops and multiple edges.〔 is inconsistent about whether to allow self-loops and multiple adjacencies: he writes on p. 76 that "parallel edges and loops are allowed" but on p. 77 he states that "a graph is a forest if and only if it does not contain the triangle ''K''3 as a minor", true only for simple graphs.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Graph minor」の詳細全文を読む スポンサード リンク
|